/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.stack;

import java.util.Stack;

/**
 * <p>
 * O(1)时间获得最小栈
 * 核心是利用一个辅助栈进行操作
 * </p>
 * @author towan
 * @email tongwenzide@163.com
 * 2015年5月17日
 */
public class MinStack {
    private Stack<Integer> stack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();
    /**
     * 栈中塞入元素
     * @param x
     * @author towan
     * 2015年5月17日
     */
    public void push(int x) {
        stack.push(x);
        if(minStack.size()==0 || x<minStack.peek()){
            minStack.push(x);
        }else{
            minStack.push(minStack.peek());
        }
    }
    /**
     * 栈元素去除
     * @author towan
     * 2015年5月17日
     */
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    /**
     * 获得栈顶的元素
     * @return
     * @author towan
     * 2015年5月17日
     */
    public int top() {
        return stack.peek();
    }
    /**
     * 获得最小元素
     * @return
     * @author towan
     * 2015年5月17日
     */
    public int getMin() {
        return minStack.peek();
    }
    
    public static void main(String[] args) {
        MinStack stack = new MinStack();
        stack.push(2);
        stack.push(3);
        stack.push(1);
        System.out.println("min:"+stack.getMin()+"\tcur:"+stack.top());
        stack.push(18);
        stack.push(6);
        System.out.println("min:"+stack.getMin()+"\tcur:"+stack.top());
        stack.pop();
        System.out.println("min:"+stack.getMin()+"\tcur:"+stack.top());
        stack.pop();
        System.out.println("min:"+stack.getMin()+"\tcur:"+stack.top());
        stack.push(3);
        System.out.println("min:"+stack.getMin()+"\tcur:"+stack.top());
        stack.pop();
        stack.pop();
        System.out.println("min:"+stack.getMin()+"\tcur:"+stack.top());
    }
}
